package com.xinwei.leetcode.数组;

import com.sun.xml.internal.txw2.output.DumpSerializer;

import java.util.*;

// https://leetcode-cn.com/problems/permutations-ii/

// 和46相比，只要考虑怎么去掉重复就行
//要解决重复问题，我们只要设定一个规则，保证在填第 depth 个数的时候重复数字只会被填入一次即可。而在本题解中，我们选择对原数组排序，保证相同的
//数字都相邻，然后每次填入的数一定是这个数所在重复数集合中「从左往右第一个未被填过的数字」，即如下的判断条件：
//
//if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
//    continue;
//}
//这个判断条件保证了对于重复数的集合，一定是从左往右逐个填入的。
//
//假设我们有 33 个重复数排完序后相邻，那么我们一定保证每次都是拿从左往右第一个未被填过的数字，即整个数组的状态其实是保证了 [未填入，未填入，未填入]
//到 [填入，未填入，未填入]，再到 [填入，填入，未填入]，最后到 [填入，填入，填入] 的过程的，因此可以达到去重的目标。
public class _47_全排列II {
    List<List<Integer>> lists = new ArrayList<>();

    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        int len = nums.length;
        Deque deque = new LinkedList<Integer>(); // 记录已经排列的数
        boolean[] used = new boolean[len]; // 记录数组中的哪些数已经被用过,如果不用这个状态变量，每一次判断哪些数用过都得遍历一次数组，经典空间换时间
        dfs(nums, len, 0, deque, used);
        return lists;
    }

    private void dfs(int[] nums, int len, int depth, Deque deque, boolean[] used) {
        if (depth == len) {
            // 深度等于数组长度，排列完毕，
            lists.add(new ArrayList<>(deque));
            return;
        }

        for (int i = 0; i < len; i++) {
            if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) {
                // 如果这个数用过或者与这个数相等的数没被用过
                continue;
            }
            deque.push(nums[i]);
            used[i] = true;
            dfs(nums, len, depth + 1, deque, used);
            // 排列完，重置状态
            deque.pop();
            used[i] = false;
        }
    }
}
